#! -*- encoding=utf-8 -*-
"""
实现双向链表： 实现链表节点：可以存放key-value数据 ==》实现双向链表（1.往头部增加节点 2.往尾部增加节点
3.删除任意节点 4.增加任意节点 5.弹出尾部节点 6.弹出头部节点）
"""


# 定义结点
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = key
        self.prev = None
        self.next = None

    def __str__(self):
        val = '(%d: %d)' % (self.key, self.value)
        return val

    def __repr__(self):
        val = '(%d: %d)' % (self.key, self.value)
        return val


# 实现双向链表
class DoubleLinkList:
    def __init__(self, capacity=0xffff):
        self.capacity = capacity  # 链表容量
        self.head = None  # 头指针
        self.tail = None  # 尾指针
        self.size = 0  # 链表已经存放了多少

    # 从头部添加结点
    def __add__head(self, node):
        if not self.head:
            self.head = node
            self.tail = node
            self.head.next = None
            self.head.prev = None
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
            self.head.prev = None
        self.size += 1
        return node

    # 从尾部添加结点
    def __add__tail(self, node):
        if not self.tail:
            self.head = node
            self.tail = node
            self.tail.next = None
            self.tail.prev = None
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
            self.tail.next = None
        self.size += 1
        return node

    # 尾部删除结点
    def __del_tail(self):
        if not self.tail:
            return
        node = self.tail
        if node.prev:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            self.head = self.tail = None
        self.size -= 1
        return node

    # 头部删除结点
    def __del_head(self):
        if not self.head:
            return
        node = self.head
        if node.next:
            self.head = node.next
            self.head.prev = None
        else:
            self.head = self.tail = None
        self.size -= 1
        return node

    # 删除任意结点
    def __remove(self, node):
        if not node:
            node = self.tail  # 如果node为None, 默认删除尾部结点
        if node == self.tail:
            # 为了保证函数功能的单一性，头部删除和尾部删除要单独写一个函数
            self.__del_tail()
        elif node == self.head:
            self.__del_head()
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
        self.size -= 1
        return node

    # 弹出头部操作
    def pop(self):
        return self.__del_head()

    # 默认尾部插入
    def append(self, node):
        return self.__add__tail(node)

    def append_front(self, node):
        return self.__add__head(node)

    def remove(self, node=None):
        return self.__remove(node)

    def print(self):
        p = self.head
        line = ''
        while p:
            line += '%s' % p
            p = p.next
            if p:
                line += '=>'
        print(line)


if __name__ == '__main__':
    l = DoubleLinkList(10)
    nodes = []
    for i in range(10):
        node = Node(i, i)
        nodes.append(node)
    l.append(nodes[0])
    l.print()
    l.append(nodes[1])
    l.print()
    l.pop()
    l.print()
    l.append(nodes[2])
    l.print()
    l.append_front(nodes[4])
    l.print()
    l.remove()
    l.print()
